package main

import (
    "fmt"
)

// Direction mappings
var DIRECTIONS = map[rune][2]int{
    'U': {-1, 0},
    'D': {1, 0},
    'L': {0, -1},
    'R': {0, 1},
}

var TRANSPORTERS = map[rune]bool{
    'U': true,
    'D': true,
    'L': true,
    'R': true,
}

func solution(N, M int, data [][]rune) int {
    visited := make([][]bool, N)
    for i := range visited {
        visited[i] = make([]bool, M)
    }

    queue := [][2]int{}

    // Initialize: find all exits 'O'
    for i := 0; i < N; i++ {
        for j := 0; j < M; j++ {
            if data[i][j] == 'O' {
                queue = append(queue, [2]int{i, j})
                visited[i][j] = true
            }
        }
    }

    reachableCount := 0

    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]
        x, y := current[0], current[1]
        reachableCount++

        // Check four directions
        for _, dir := range DIRECTIONS {
            nx := x + dir[0]
            ny := y + dir[1]

            // Boundary check
            if nx >= 0 && nx < N && ny >= 0 && ny < M && !visited[nx][ny] {
                cell := data[nx][ny]

                // If it's a transporter
                if TRANSPORTERS[cell] {
                    tDir := DIRECTIONS[cell]
                    // Check if this transporter can send to current position
                    if nx+tDir[0] == x && ny+tDir[1] == y {
                        visited[nx][ny] = true
                        queue = append(queue, [2]int{nx, ny})
                    }
                } else {
                    // Normal cell
                    visited[nx][ny] = true
                    queue = append(queue, [2]int{nx, ny})
                }
            }
        }
    }

    return N*M - reachableCount
}

func main() {
    // Test Case 1
    data1 := [][]rune{
        {'.', '.', '.', '.', '.'},
        {'.', 'R', 'R', 'D', '.'},
        {'.', 'U', '.', 'D', 'R'},
        {'.', 'U', 'L', 'L', '.'},
        {'.', '.', '.', '.', 'O'},
    }
    fmt.Println(solution(5, 5, data1) == 10) // true

    // Test Case 2
    data2 := [][]rune{
        {'.', 'R', '.', 'O'},
        {'U', '.', 'L', '.'},
        {'.', 'D', '.', '.'},
        {'.', '.', 'R', 'D'},
    }
    fmt.Println(solution(4, 4, data2) == 2) // true

    // Test Case 3
    data3 := [][]rune{
        {'.', 'U', 'O'},
        {'L', '.', 'R'},
        {'D', '.', '.'},
    }
    fmt.Println(solution(3, 3, data3) == 8) // true
}